package main

import "fmt"

// 最小覆盖子串
func main() {
	s := "ADOBECODEBANC"
	t := "ABC"

	s, t = "aa", "aa"
	res := minWindow(s, t)
	fmt.Println(res)
}

func minWindow(s string, t string) string {
	tByte := []byte(t)
	tMap := map[byte]int{}
	for _, b := range tByte {
		tMap[b]++
	}

	var resByte []byte

	sByte := []byte(s)
	n := len(s)
	l := 0
	r := 0
	meetByteNum := 0 //满足的字符数量
	searchMap := map[byte]int{}

	for r < n {
		// if sByte add to window
		b := sByte[r]
		r++
		if tMap[b] == 0 {
			continue
		}
		// 是目标字符
		searchMap[b]++
		if searchMap[b] != tMap[b] {
			continue
		}

		//有一个字符满足了
		meetByteNum++
		for meetByteNum == len(tMap) {
			if resByte == nil || len(resByte) > (r-l) {
				resByte = sByte[l:r]
			}
			b2 := sByte[l]
			l++
			if tMap[b2] == 0 {
				continue //非目标字符
			}
			if searchMap[b2] == tMap[b2] {
				meetByteNum--
			}
			searchMap[b2]--
		}
	}
	return string(resByte)
}
